<!DOCTYPE html>
<html lang="en">
	<meta charset="UTF-8">
	<title>LCT模板</title>
<pre>node son[nmax][2],fa[nmax];
bool rev[nmax];
int val[nmax],sum[nmax];
#define lson(x) (son[x][0])
#define rson(x) (son[x][1])
#define root(x) (lson(fa[x])!=x&&rson(fa[x])!=x)
#define side(x) (rson(fa[x])==x)
inline void pd(node x) {if(!rev[x])return;swap(lson(x),rson(x));rev[lson(x)]^=1;rev[rson(x)]^=1;rev[x]=0;}
inline void pu(node x) {sum[x]=sum[lson(x)]^sum[rson(x)]^val[x];}
inline void rot(node x) {node y=fa[x],z=fa[y];bool d=side(x);if(!root(y))son[z][side(y)]=x;fa[x]=z;son[y][d]=son[x][!d];fa[son[x][!d]]=y;son[x][!d]=y;fa[y]=x;pu(y);pu(x);}
inline void spl(node x) {static node sta[nmax];static int top;node y=sta[top=1]=x;while(!root(y))sta[++top]=y=fa[y];while(top)pd(sta[top--]);for(y=fa[x];!root(x);rot(x),y=fa[x])if(!root(y))rot(side(x)==side(y)?y:x);pu(x);}

inline void acc(node x) {for(node y=0;x;y=x,x=fa[x])spl(x),rson(x)=y;}
inline node fro(node x) {acc(x);spl(x);while(lson(x))x=lson(x);spl(x);return x;}
inline void mro(node x) {acc(x);spl(x);rev[x]^=1;}
inline void lin(node x, node y) {mro(x);if(fro(y)==x)return;fa[x]=y;}
inline void cut(node x, node y) {mro(x);if(fro(y)!=x||fa[y]!=x||lson(y))return;fa[y]=rson(x)=0;}
inline void get(node x, node y) {mro(x);acc(y);spl(y);}
#undef root
#undef side</pre></html>